﻿//============================================================
// Project: DigitalFactory
// Author: Administrator@DESKTOP-IE3FPT7
// Datetime: 2021-03-22 19:53:45
// Description: TODO >> This is a script Description.
//============================================================

using System;
using System.Collections.Generic;

namespace NodePathFinder.Script
{
    [Serializable]
    public class Graph
    {
        private List<Edge>[] _Edges;
        private DijkStra dijkStra;
        public int VertexCount { get; private set; }

        /// <summary>
        /// 此条线路是否被占用
        /// </summary>
        public bool IsBusy { get; set; }

        public Graph(int count)
        {
            VertexCount = count;
            _Edges = new List<Edge>[count];
            for (int i = 0; i < count; i++)
            {
                _Edges[i] = new List<Edge>();
            }
            dijkStra = new DijkStra(this);
        }

        public void AddEdge(Edge edge)
        {
            _Edges[edge.Vertex1].Add(edge);
            _Edges[edge.Vertex2].Add(edge);
        }

        /// <summary>
        /// 防止调用者获取到Queue乱操作
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public Edge[] GetADJMarix(int index)
        {
            return _Edges[index].ToArray();
        }

        public int[] DijkStraSearch(int start, int end)
        {
            return dijkStra.Search(start, end);
        }
    }

    [Serializable]
    public class Edge
    {
        public int Vertex1 { get; private set; }
        public int Vertex2 { get; private set; }
        public double Weight { get; protected set; }


        public Edge(int v1, int v2, double weight)
        {
            this.Vertex1 = v1;
            this.Vertex2 = v2;
            this.Weight = weight;
        }

        public int GetVertex()
        {
            return Vertex1;
        }

        public int GetOthers(int vertex)
        {
            return vertex == Vertex1 ? Vertex2 : Vertex1;
        }
    }

    public class DijkStra
    {
        private int[] _Sured;
        public double[] _DisList { get; private set; }
        private Graph _Graph;
        private int[] _Path;
        private Dictionary<int, int[]> PathCache = new Dictionary<int, int[]>();

        public DijkStra(Graph graph)
        {
            this._Sured = new int[graph.VertexCount];
            this._DisList = new double[graph.VertexCount];

            this._Graph = graph;

        }

        public int[] Search(int start, int end)
        {
            if (start == end)
            {
                return null;
            }
            if (!PathCache.ContainsKey(start))
            {
                Search(start);
                PathCache.Add(start, this._Path);
            }
            int[] path = PathCache[start];
            List<int> traceBackList = new List<int>();
            while (end != start)
            {
                traceBackList.Add(end);
                if (path[end] == -1)
                {
                    //寻路不成功
                    return null;
                }
                end = path[end];
            }
            traceBackList.Reverse();
            return traceBackList.ToArray();
        }

        private void Search(int start)
        {
            this._Path = new int[_Graph.VertexCount];
            for (int i = 0; i < _DisList.Length; i++)
            {
                _DisList[i] = double.MaxValue;
                _Path[i] = -1;
                _Sured[i] = 0;
            }
            _DisList[start] = 0;
            _Sured[start] = 1;

            Edge[] edges = _Graph.GetADJMarix(start);
            Recurve(edges, start);
        }


        private void Recurve(Edge[] aDJMarix, int index)
        {
            for (int i = 0; i < aDJMarix.Length; i++)
            {
                int otherIndex = aDJMarix[i].GetOthers(index);
                double others = _DisList[otherIndex];
                double moreNear = aDJMarix[i].Weight + _DisList[index];
                if (double.IsInfinity(others) || moreNear < _DisList[otherIndex])
                {
                    _DisList[otherIndex] = moreNear;
                    _Path[otherIndex] = index;
                }
            }
            _Sured[index] = 1;
            double minExpect = -1;
            for (int i = 0; i < _DisList.Length; i++)
            {
                int n = Array.IndexOf(_DisList, _DisList[i]);
                if (_Sured[n] == 1)
                {
                    continue;
                }
                if (minExpect == -1)
                {
                    minExpect = _DisList[i];
                }
                minExpect = minExpect < _DisList[i] ? minExpect : _DisList[i];
            }
            int next = Array.IndexOf(_DisList, minExpect);
            if (next != -1 &&  _Sured[next] != 1)
            {
                Recurve(_Graph.GetADJMarix(next), next);
            }
        }
    }
}
